/**
 * 面试题04：二维数组中的查找
 */
public class Offer_04 {
    /**
     * 方法二：线性查找
     * <p>
     * 题目：每一行从左到右递增，每一列从上到下递增
     * <p>
     * 算法：从右上角或者左下角出发，每次消掉一行或一列
     * <p>
     * 时间复杂度：O(row+col)
     * <p>
     * 空间复杂度：O(1)
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length, col = matrix[0].length;
        int i = 0, j = col - 1;
        while (i < row && j >= 0) {
            int num = matrix[i][j];
            if (num > target) {
                j--;
            } else if (num < target) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 方法一：暴力法
     * <p>
     * 逐个检查每个元素
     * <p>
     * 时间复杂度：O(row*col)
     * <p>
     * 空间复杂度：O(1)
     */
    public boolean findNumberIn2DArray1(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length, col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Offer_04 solution = new Offer_04();
        int[][] matrix = { { 1, 4, 7, 11, 15 }, { 2, 5, 8, 12, 19 }, { 3, 6, 9, 16, 22 }, { 10, 13, 14, 17, 24 },
                { 18, 21, 23, 26, 30 } };
        boolean ans = solution.findNumberIn2DArray(matrix, 5);
        System.out.println(ans);
        ans = solution.findNumberIn2DArray(matrix, 20);
        System.out.println(ans);
    }
}
